package org.example.myleet.p1403;

import java.util.*;

public class Solution {
    public List<Integer> minSubsequence(int[] nums) {
        Arrays.sort(nums);
        int sum = 0;
        for (int num : nums) {
            sum += num;
        }
        int subSum = 0;
        List<Integer> res = new ArrayList<>();
        for (int i = nums.length - 1; i >= 0; --i) {
            res.add(nums[i]);
            subSum += nums[i];
            sum -= nums[i];
            if (subSum > sum) {
                break;
            }
        }
        return res;
    }
}

//public class Solution {
//    public List<Integer> minSubsequence(int[] nums) {
//        int[] copy = new int[nums.length];
//        System.arraycopy(nums, 0, copy, 0, nums.length);
//        Arrays.sort(copy);
//        int sum = 0;
//        for (int num : copy) {
//            sum += num;
//        }
//        int subSum = 0;
//        Map<Integer, Integer> candidates = new HashMap<>();
//        for (int i = copy.length - 1; i >= 0; --i) {
//            candidates.put(copy[i], candidates.getOrDefault(copy[i], 0) + 1);
//            subSum += copy[i];
//            sum -= copy[i];
//            if (subSum > sum) {
//                break;
//            }
//        }
//        List<Integer> res = new ArrayList<>();
//        for (int num : nums) {
//            if (candidates.containsKey(num)) {
//                res.add(num);
//                int count = candidates.get(num) - 1;
//                if (count <= 0) {
//                    candidates.remove(num);
//                } else {
//                    candidates.put(num, count);
//                }
//            }
//        }
//        return res;
//    }
//}
